#include "main/utils.h"
using namespace std;

bool setColor1(const vector<vector<int>>& grid,
               vector<int>& colors,
               int i,
               int color) {
  colors[i] = color;
  deque<int> deque;
  deque.push_back(i);
  while (!deque.empty()) {
    auto cur_node = deque.front();
    deque.pop_front();
    for (auto next_node : grid[cur_node]) {
      if (colors[next_node] == -1) {
        colors[next_node] = 1 - colors[cur_node];
        deque.push_back(next_node);
      } else if (colors[next_node] == colors[cur_node]) {
        return false;
      }
    }
  }
  return true;
}

bool setColor2(const vector<vector<int>>& grid,
               vector<int>& colors,
               int i,
               int color) {
  colors[i] = color;
  for (auto next_node : grid[i]) {
    if (colors[next_node] == color) {
      return false;
    } else if (colors[next_node] == -1) {
      if (!setColor2(grid, colors, next_node, 1 - color)) {
        return false;
      } 
    }
  }
  return true;
}

bool isBipartite(const vector<vector<int>> &grid, decltype(setColor1) func) {
  int size = grid.size();
  vector<int> color(size, -1);
  for (int i = 0; i < size; ++i) {
    if (color[i] == -1) {
      if (!func(grid, color, i, 0)) {
        return false;
      }
    }
  }
  return true;
}

int main() {
  vector<vector<int>> grid = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
  vector<vector<int>> grid1 = {{1, 2, 3}, {0, 2}, {0, 1, 3}, {0, 2}};
  cout << isBipartite(grid, setColor1) << endl;
  cout << isBipartite(grid, setColor2) << endl;

  cout << isBipartite(grid1, setColor1) << endl;
  cout << isBipartite(grid1, setColor2) << endl;

  return 0;
}
